﻿using System;
using System.Collections.Generic;

namespace QSharp.Scheme.Classical.Sequential
{
    public static class BinarySearch
    {
        /**
         * <summary>
         *  `T' is characterized by or comparable to key `Key'
         *  The list is sorted in ascending order with respect to its 
         *  items' key
         *  
         *  Of course `T' and `Key' could be the same, reducing the problem 
         *  to a trivial case.
         *  
         *  It is either where the key is found (if applicable) or where
         *  an entry with key should be inserted at, the method returns true
         *  or false correspondingly.
         * </summary>
         */
        public static bool Search<T>(IList<T> list, IComparable<T> comparer, out int index)
        {
            int b = 0, e = list.Count;

            for (; ; )
            {
                if (b == e)
                {
                    index = b;
                    return false;
                }

                index = (b + e) / 2;
                T t = list[index];

                int cmp = comparer.CompareTo(t);
                if (cmp < 0)
                {   // targetKey < list[index]
                    e = index;
                }
                else if (cmp > 0)
                {   // list[index] < targetKey
                    b = index + 1;
                }
                else
                {   // match
                    return true;
                }
            }
        }
    }
}
